package com.demo.java.OD551_600.OD598;

import java.util.Scanner;
import java.util.LinkedList;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【迷宫问题(B卷-100分)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146587490
 */
public class OdMain {
    // 用于存储输出的结果
    public static String output_str = "";

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        // 读取矩阵的大小
        String input_str = in.nextLine();
        String[] tmp2 = input_str.split(" ");
        int[] nums = new int[tmp2.length];
        for (int i = 0; i < tmp2.length; i++) {
            nums[i] = Integer.parseInt(tmp2[i]);
        }
        int n = nums[0];  // 矩阵的行数
        int m = nums[1];  // 矩阵的列数

        // 创建矩阵
        int[][] matrix = new int[n][m];

        // 读取矩阵数据
        for (int i = 0; i < n; i++) {
            String input_str1 = in.nextLine();
            String[] tmp1 = input_str1.split(" ");
            int[] nums1 = new int[tmp1.length];
            for (int k = 0; k < tmp1.length; k++) {
                nums1[k] = Integer.parseInt(tmp1[k]);
            }
            for (int j = 0; j < m; j++) {
                matrix[i][j] = nums1[j];
            }
        }

        // 从起点开始深度优先搜索
        dfs(0, 0, new LinkedList<>(), n, m, matrix);

        // 输出最终结果
        output_str += "(" + (n - 1) + "," + (m - 1) + ")";
        System.out.println(output_str);
    }

    // 深度优先搜索函数
    public static void dfs(int x, int y, LinkedList<String> path, int n, int m, int[][] matrix) {
        // 到达终点时，输出当前路径
        if (x == n - 1 && y == m - 1) {
            for (String p : path) {
                output_str += p + "\n";  // 将路径坐标加入输出字符串
            }
            return;
        }

        // 试探向下走
        if (x + 1 < n && matrix[x + 1][y] == 0) {
            path.add("(" + x + "," + y + ")");
            matrix[x][y] = 2;  // 标记该位置为已访问
            dfs(x + 1, y, path, n, m, matrix);
            path.removeLast();  // 回溯
        }

        // 试探向上走
        if (x - 1 >= 0 && matrix[x - 1][y] == 0) {
            path.add("(" + x + "," + y + ")");
            matrix[x][y] = 2;
            dfs(x - 1, y, path, n, m, matrix);
            path.removeLast();
        }

        // 试探向右走
        if (y + 1 < m && matrix[x][y + 1] == 0) {
            path.add("(" + x + "," + y + ")");
            matrix[x][y] = 2;
            dfs(x, y + 1, path, n, m, matrix);
            path.removeLast();
        }

        // 试探向左走
        if (y - 1 >= 0 && matrix[x][y - 1] == 0) {
            path.add("(" + x + "," + y + ")");
            matrix[x][y] = 2;
            dfs(x, y - 1, path, n, m, matrix);
            path.removeLast();
        }
    }
}